{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Title: #Cut Off Trees for Golf Event"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Difficulty: #Hard"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Category Title: #Algorithms"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Tag Slug: #breadth-first-search #array #matrix #heap-priority-queue"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Name Translated: #广度优先搜索 #数组 #矩阵 #堆（优先队列）"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solution Name: cutOffTree"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Title: #为高尔夫比赛砍树"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Content:\n",
    "<p>你被请来给一个要举办高尔夫比赛的树林砍树。树林由一个 <code>m x n</code> 的矩阵表示， 在这个矩阵中：</p>\n",
    "\n",
    "<ul>\n",
    "\t<li><code>0</code> 表示障碍，无法触碰</li>\n",
    "\t<li><code>1</code> 表示地面，可以行走</li>\n",
    "\t<li><code>比 1 大的数</code> 表示有树的单元格，可以行走，数值表示树的高度</li>\n",
    "</ul>\n",
    "\n",
    "<p>每一步，你都可以向上、下、左、右四个方向之一移动一个单位，如果你站的地方有一棵树，那么你可以决定是否要砍倒它。</p>\n",
    "\n",
    "<p>你需要按照树的高度从低向高砍掉所有的树，每砍过一颗树，该单元格的值变为 <code>1</code>（即变为地面）。</p>\n",
    "\n",
    "<p>你将从 <code>(0, 0)</code> 点开始工作，返回你砍完所有树需要走的最小步数。 如果你无法砍完所有的树，返回 <code>-1</code> 。</p>\n",
    "\n",
    "<p>可以保证的是，没有两棵树的高度是相同的，并且你至少需要砍倒一棵树。</p>\n",
    "\n",
    "<p> </p>\n",
    "\n",
    "<p><strong>示例 1：</strong></p>\n",
    "<img alt=\"\" src=\"https://assets.leetcode.com/uploads/2020/11/26/trees1.jpg\" style=\"width: 242px; height: 242px;\" />\n",
    "<pre>\n",
    "<strong>输入：</strong>forest = [[1,2,3],[0,0,4],[7,6,5]]\n",
    "<strong>输出：</strong>6\n",
    "<strong>解释：</strong>沿着上面的路径，你可以用 6 步，按从最矮到最高的顺序砍掉这些树。</pre>\n",
    "\n",
    "<p><strong>示例 2：</strong></p>\n",
    "<img alt=\"\" src=\"https://assets.leetcode.com/uploads/2020/11/26/trees2.jpg\" style=\"width: 242px; height: 242px;\" />\n",
    "<pre>\n",
    "<strong>输入：</strong>forest = [[1,2,3],[0,0,0],[7,6,5]]\n",
    "<strong>输出：</strong>-1\n",
    "<strong>解释：</strong>由于中间一行被障碍阻塞，无法访问最下面一行中的树。\n",
    "</pre>\n",
    "\n",
    "<p><strong>示例 3：</strong></p>\n",
    "\n",
    "<pre>\n",
    "<strong>输入：</strong>forest = [[2,3,4],[0,0,5],[8,7,6]]\n",
    "<strong>输出：</strong>6\n",
    "<strong>解释：</strong>可以按与示例 1 相同的路径来砍掉所有的树。\n",
    "(0,0) 位置的树，可以直接砍去，不用算步数。\n",
    "</pre>\n",
    "\n",
    "<p> </p>\n",
    "\n",
    "<p><strong>提示：</strong></p>\n",
    "\n",
    "<ul>\n",
    "\t<li><code>m == forest.length</code></li>\n",
    "\t<li><code>n == forest[i].length</code></li>\n",
    "\t<li><code>1 <= m, n <= 50</code></li>\n",
    "\t<li><code>0 <= forest[i][j] <= 10<sup>9</sup></code></li>\n",
    "</ul>\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Description: [cut-off-trees-for-golf-event](https://leetcode.cn/problems/cut-off-trees-for-golf-event/description/)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solutions: [cut-off-trees-for-golf-event](https://leetcode.cn/problems/cut-off-trees-for-golf-event/solutions/)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "test_cases = ['[[1,2,3],[0,0,4],[7,6,5]]', '[[1,2,3],[0,0,0],[7,6,5]]', '[[2,3,4],[0,0,5],[8,7,6]]']"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "DIRS = (0, 1), (1, 0), (0, -1), (-1, 0)\n",
    "class Solution:\n",
    "    def cutOffTree(self, forest: List[List[int]]) -> int:\n",
    "        m, n = len(forest), len(forest[0])\n",
    "        trees = sorted((forest[i][j], i, j) for i, j in product(range(m), range(n)) if forest[i][j] > 1)\n",
    "\n",
    "        def bfs(start, end):\n",
    "            queue = deque([(start, 0)])\n",
    "            explored = [list(r) for r in forest]\n",
    "            while queue:\n",
    "                cur, cost = queue.popleft()\n",
    "                if cur == end:\n",
    "                    return cost\n",
    "                x, y = cur\n",
    "                cost += 1\n",
    "                for dx, dy in DIRS:\n",
    "                    if 0 <= (nx := x + dx) < m and 0 <= (ny := y + dy) < n and explored[nx][ny]:\n",
    "                        explored[nx][ny] = 0\n",
    "                        queue.append(((nx, ny), cost))\n",
    "            return -1\n",
    "        \n",
    "        ans = bfs((0, 0), trees[0][1:])\n",
    "        for a, b in pairwise(trees):\n",
    "            if (res := bfs(a[1:], b[1:])) == -1:\n",
    "                return -1\n",
    "            ans += res\n",
    "        return ans\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def cutOffTree(self, forest: List[List[int]]) -> int:\n",
    "        if not forest or not forest[0]: return 0\n",
    "        m, n = len(forest), len(forest[0])\n",
    "        trees = []\n",
    "        \n",
    "        for i in range(m):\n",
    "            for j in range(n):\n",
    "                if forest[i][j] > 1:\n",
    "                    heappush(trees, (forest[i][j], i, j))\n",
    "        \n",
    "        startX, startY = 0, 0\n",
    "        totalSteps = 0\n",
    "        while trees:\n",
    "            tree, endX, endY = heappop(trees)\n",
    "            steps = self.bfs(forest, startX, startY, endX, endY)\n",
    "            if steps == -1:\n",
    "                return -1\n",
    "            totalSteps += steps\n",
    "            startX, startY = endX, endY\n",
    "        \n",
    "        return totalSteps\n",
    "\n",
    "    def bfs(self, forest, startX, startY, endX, endY):\n",
    "        if startX == endX and startY == endY:\n",
    "            return 0\n",
    "            \n",
    "        m, n = len(forest), len(forest[0])\n",
    "        visited = [[False] * n for _ in range(m)]\n",
    "        q = deque([(startX, startY, 0)])\n",
    "        visited[startX][startY] = True\n",
    "        dirs = [-1, 0, 1, 0, -1]\n",
    "        \n",
    "        while q:\n",
    "            x, y, steps = q.popleft()\n",
    "            for k in range(4):\n",
    "                newX, newY = x + dirs[k], y + dirs[k+1]\n",
    "                if 0 <= newX < m and 0 <= newY < n and not visited[newX][newY] and forest[newX][newY] != 0:\n",
    "                    if newX == endX and newY == endY:\n",
    "                        return steps + 1\n",
    "                    q.append((newX, newY, steps + 1))\n",
    "                    visited[newX][newY] = True\n",
    "        \n",
    "        return -1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "DIRS = (0, 1), (1, 0), (0, -1), (-1, 0)\n",
    "class Solution:\n",
    "    def cutOffTree(self, forest: List[List[int]]) -> int:\n",
    "        m, n = len(forest), len(forest[0])\n",
    "        trees = sorted((forest[i][j], i, j) for i, j in product(range(m), range(n)) if forest[i][j] > 1)\n",
    "\n",
    "        def bfs(start, end):\n",
    "            queue = deque([(start, 0)])\n",
    "            explored = [ list(r) for r in forest]\n",
    "            while queue:\n",
    "                cur, cost = queue.popleft()\n",
    "                if cur == end:\n",
    "                    return cost\n",
    "                x, y = cur\n",
    "                cost += 1\n",
    "                for dx, dy in DIRS:\n",
    "                    if 0 <= (nx := x + dx) < m and 0 <= (ny := y + dy) < n and explored[nx][ny]:\n",
    "                        explored[nx][ny] = 0\n",
    "                        queue.append(((nx, ny), cost))\n",
    "            return -1\n",
    "        \n",
    "        ans = bfs((0, 0), trees[0][1:])\n",
    "        for a, b in pairwise(trees):\n",
    "            if (res := bfs(a[1:], b[1:])) == -1:\n",
    "                return -1\n",
    "            ans += res\n",
    "        return ans\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "DIRS = (0, 1), (1, 0), (0, -1), (-1, 0)\n",
    "class Solution:\n",
    "    def cutOffTree(self, forest: List[List[int]]) -> int:\n",
    "        m, n = len(forest), len(forest[0])\n",
    "        trees = sorted((forest[i][j], i, j) for i, j in product(range(m), range(n)) if forest[i][j] > 1)\n",
    "\n",
    "        def bfs(start, end):\n",
    "            queue = deque([(start, 0)])\n",
    "            explored = [ list(r) for r in forest]\n",
    "            while queue:\n",
    "                cur, cost = queue.popleft()\n",
    "                if cur == end:\n",
    "                    return cost\n",
    "                x, y = cur\n",
    "                for dx, dy in DIRS:\n",
    "                    if 0 <= (nx := x + dx) < m and 0 <= (ny := y + dy) < n and explored[nx][ny]:\n",
    "                        explored[nx][ny] = 0\n",
    "                        queue.append(((nx, ny), cost+1))\n",
    "            return -1\n",
    "        \n",
    "        ans = bfs((0, 0), trees[0][1:])\n",
    "        for a, b in pairwise(trees):\n",
    "            if (res := bfs(a[1:], b[1:])) == -1:\n",
    "                return -1\n",
    "            ans += res\n",
    "        return ans\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "DIRS = (0, 1), (1, 0), (0, -1), (-1, 0)\n",
    "class Solution:\n",
    "    def cutOffTree(self, forest: List[List[int]]) -> int:\n",
    "        m, n = len(forest), len(forest[0])\n",
    "        trees = sorted((forest[i][j], i, j) for i, j in product(range(m), range(n)) if forest[i][j] > 1)\n",
    "\n",
    "        def bfs(start, end):\n",
    "            queue = deque([(start, 0)])\n",
    "            explored = [list(r) for r in forest]\n",
    "            while queue:\n",
    "                cur, cost = queue.popleft()\n",
    "                if cur == end:\n",
    "                    return cost\n",
    "                x, y = cur\n",
    "                cost += 1\n",
    "                for dx, dy in DIRS:\n",
    "                    if 0 <= (nx := x + dx) < m and 0 <= (ny := y + dy) < n and explored[nx][ny]:\n",
    "                        explored[nx][ny] = 0\n",
    "                        queue.append(((nx, ny), cost))\n",
    "            return -1\n",
    "        \n",
    "        ans = bfs((0, 0), trees[0][1:])\n",
    "        for a, b in pairwise(trees):\n",
    "            if (res := bfs(a[1:], b[1:])) == -1:\n",
    "                return -1\n",
    "            ans += res\n",
    "        return ans\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def cutOffTree(self, forest: List[List[int]]) -> int:\n",
    "        n, m = len(forest), len(forest[0])\n",
    "        def bfs(i, j, ti, tj):\n",
    "            q = deque([(0, i, j)])\n",
    "            vis = {(i, j)}\n",
    "            while q:\n",
    "                d, x, y = q.popleft()\n",
    "                if x == ti and y == tj:\n",
    "                    return d\n",
    "                for xx, yy in [[x, y + 1], [x, y - 1], [x + 1, y], [x - 1, y]]:\n",
    "                    if 0 <= xx < n and 0 <= yy < m and forest[xx][yy] and (xx, yy) not in vis:\n",
    "                        q.append((d + 1, xx, yy))\n",
    "                        vis.add((xx, yy))\n",
    "            return -1\n",
    "\n",
    "        srt = sorted((h, i, j) for i, row in enumerate(forest) for j, h in enumerate(row) if h > 1)\n",
    "        ans = preI = preJ = 0\n",
    "        for _, i, j in srt:\n",
    "            d = bfs(preI, preJ, i, j)\n",
    "            if d < 0:\n",
    "                return -1\n",
    "            ans += d\n",
    "            preI, preJ = i, j\n",
    "        return ans  "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    \n",
    "    def cutOffTree(self, forest):\n",
    "        res = 0\n",
    "        fangxiangs=[[-1,0],[1,0],[0,1],[0,-1]]\n",
    "        w = len(forest[0]) # 获取有多少列\n",
    "        h = len(forest) #获取有多少行\n",
    "        tree = [ [forest[x][y],x,y] for x in range(h) for y in range(w) if forest[x][y]>1 ]\n",
    "        # 生成要砍的树\n",
    "        tree = sorted(tree, key=lambda x: x[0] ) # 对要砍的树进行排序\n",
    "        \n",
    "        def PintA2PointB_bushu(forest, diana,dianb):\n",
    "            if diana==dianb : return 0\n",
    "            jieguo=-1\n",
    "\n",
    "            flag=[ [0]*len(forest[0]) for _ in range(len(forest)) ]\n",
    "        \n",
    "            duilie = []\n",
    "            \n",
    "            duilie.append(diana)\n",
    "            flag[diana[0]][diana[1]]=1\n",
    "            \n",
    "            while duilie:\n",
    "                jieguo+=1\n",
    "                for _ in range(len(duilie)):\n",
    "                    \n",
    "                    duishou = duilie[0]\n",
    "                    duilie.pop(0)\n",
    "                    if duishou==dianb:\n",
    "                        return jieguo\n",
    "                    \n",
    "                    for fangxiang in fangxiangs:\n",
    "                        \n",
    "                        next_i,next_j = duishou[0]+fangxiang[0],duishou[1]+fangxiang[1]\n",
    "                        \n",
    "                        if 0<= next_i < h and 0<= next_j<w:\n",
    "                            \n",
    "                            if flag[next_i][next_j]==0 and forest[next_i][next_j]>0:\n",
    "                                \n",
    "                                duilie.append([next_i, next_j])\n",
    "                                \n",
    "                                flag[next_i][next_j]=1\n",
    "\n",
    "            return -1\n",
    "        res+=PintA2PointB_bushu(forest,[0,0],[tree[0][1],tree[0][2]])\n",
    "        for i in range(len(tree)-1):\n",
    "            tem = PintA2PointB_bushu(forest,tree[i][1:],tree[i+1][1:])\n",
    "            if tem == -1:\n",
    "                return -1\n",
    "            res+=tem\n",
    "        # print(res)\n",
    "        \n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def cutOffTree(self, forest: List[List[int]]) -> int:\n",
    "        m, n = len(forest), len(forest[0])\n",
    "        def bfs(x1, y1, x2, y2):\n",
    "            todo = [(0, x1 , y1)]\n",
    "            visited = {(x1,y1)}\n",
    "            while todo:\n",
    "                step, x, y = todo.pop(0)\n",
    "                if x == x2 and y == y2: return step\n",
    "\n",
    "                for _x, _y in [(0,1),(0,-1),(-1,0),(1,0)]:\n",
    "                    if 0 <= x+_x < m and 0 <= y+_y < n and forest[x+_x][y+_y]>0 and (x+_x,y+_y) not in visited: \n",
    "                        todo.append((step+1, x+_x,y+_y))\n",
    "                        visited.add((x+_x,y+_y))\n",
    "\n",
    "            return -1\n",
    "\n",
    "        trees = sorted((h, i, j) for i, row in enumerate(forest) for j, h in enumerate(row) if h > 1)\n",
    "        ans = preI = preJ = 0\n",
    "        for _, i, j in trees:\n",
    "            d = bfs(preI, preJ, i, j)\n",
    "            if d < 0:\n",
    "                return -1\n",
    "            ans += d\n",
    "            preI, preJ = i, j\n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "import heapq\r\n",
    "class Solution:\r\n",
    "    def cutOffTree(self, forest: List[List[int]]) -> int:\r\n",
    "        def bfs(sx,sy,tx,ty):   #target\r\n",
    "            if sx==tx and sy==ty:\r\n",
    "                return 0\r\n",
    "            m,n=len(forest),len(forest[0])\r\n",
    "            costed=[[float('inf')]*n for _ in range(m)]\r\n",
    "            costed[sx][sy]=abs(sx-tx)+abs(sy-ty)\r\n",
    "            pq=[]\r\n",
    "            heapq.heappush(pq,(costed[sx][sy],0,sx,sy))\r\n",
    "            while pq:\r\n",
    "                cost,d,x,y=heapq.heappop(pq)\r\n",
    "                if x==tx and y==ty:\r\n",
    "                    return d\r\n",
    "                for nx,ny in ((x-1,y),(x+1,y),(x,y-1),(x,y+1)):     #now\r\n",
    "                    if 0<=nx<m and 0<=ny<n and forest[nx][ny]:\r\n",
    "                        ncost=d+1+abs(nx-tx)+abs(ny-ty)\r\n",
    "                        if ncost<costed[nx][ny]:\r\n",
    "                            heapq.heappush(pq,(ncost,d+1,nx,ny))\r\n",
    "                            costed[nx][ny]=ncost\r\n",
    "            return -1\r\n",
    "\r\n",
    "        trees=sorted((h,i,j) for i,row in enumerate(forest) for j,h in enumerate(row) if h>1)\r\n",
    "        ans=preI=preJ=0\r\n",
    "        for _,i,j in trees:\r\n",
    "            d=bfs(preI,preJ,i,j)\r\n",
    "            if d<0:\r\n",
    "                return -1\r\n",
    "            ans+=d\r\n",
    "            preI,preJ=i,j\r\n",
    "        \r\n",
    "        return ans\r\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def cutOffTree(self, forest: List[List[int]]) -> int:\n",
    "        m,n = len(forest),len(forest[0])\n",
    "        p = [(forest[i][j],i,j) for i in range(m) for j in range(n) if forest[i][j] > 1]\n",
    "        heapify(p)\n",
    "        start = (0,0)\n",
    "        ans = 0\n",
    "        while p:   \n",
    "            _,tx,ty = heappop(p)         \n",
    "            q = deque([start])            \n",
    "            step = 0\n",
    "            visit = set()\n",
    "            visit.add(start)\n",
    "            flag = False\n",
    "            # print(tx,ty,ans)\n",
    "            while q:\n",
    "                for _ in range(len(q)):\n",
    "                    cx,cy = q.popleft()\n",
    "                    if cx == tx and cy == ty:\n",
    "                        ans += step\n",
    "                        start = (tx,ty)\n",
    "                        forest[tx][ty] = 1\n",
    "                        flag = True\n",
    "                        break\n",
    "                    for dx,dy in [(0,-1),(0,1),(-1,0),(1,0)]:\n",
    "                        nx,ny = cx+dx,cy+dy\n",
    "                        if 0<=nx<m and 0<=ny<n and (nx,ny) not in visit and forest[nx][ny]:\n",
    "                            q.append((nx,ny))\n",
    "                            visit.add((nx,ny))\n",
    "                if flag:\n",
    "                    break\n",
    "                step += 1\n",
    "            else:\n",
    "                return -1\n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    \n",
    "    def cutOffTree(self, forest):\n",
    "        res = 0\n",
    "        fangxiangs=[[-1,0],[1,0],[0,1],[0,-1]]\n",
    "        w = len(forest[0]) # 获取有多少列\n",
    "        h = len(forest) #获取有多少行\n",
    "        tree = [ [forest[x][y],x,y] for x in range(h) for y in range(w) if forest[x][y]>1 ]\n",
    "        # 生成要砍的树\n",
    "        tree = sorted(tree, key=lambda x: x[0] ) # 对要砍的树进行排序\n",
    "        \n",
    "        def PintA2PointB_bushu(forest, diana,dianb):\n",
    "            if diana==dianb : return 0\n",
    "            jieguo=-1\n",
    "\n",
    "            flag=[ [0]*len(forest[0]) for _ in range(len(forest)) ]\n",
    "        \n",
    "            duilie = []\n",
    "            \n",
    "            duilie.append(diana)\n",
    "            flag[diana[0]][diana[1]]=1\n",
    "            \n",
    "            while duilie:\n",
    "                jieguo+=1\n",
    "                for _ in range(len(duilie)):\n",
    "                    \n",
    "                    duishou = duilie[0]\n",
    "                    duilie.pop(0)\n",
    "                    if duishou==dianb:\n",
    "                        return jieguo\n",
    "                    \n",
    "                    for fangxiang in fangxiangs:\n",
    "                        \n",
    "                        next_i,next_j = duishou[0]+fangxiang[0],duishou[1]+fangxiang[1]\n",
    "                        \n",
    "                        if 0<= next_i < h and 0<= next_j<w:\n",
    "                            \n",
    "                            if flag[next_i][next_j]==0 and forest[next_i][next_j]>0:\n",
    "                                \n",
    "                                duilie.append([next_i, next_j])\n",
    "                                \n",
    "                                flag[next_i][next_j]=1\n",
    "\n",
    "            return -1\n",
    "        prex, prey=0, 0\n",
    "        for t in tree:\n",
    "            val,sx,sy = t\n",
    "            tmp = PintA2PointB_bushu(forest,[prex,prey],[sx,sy])\n",
    "            if tmp==-1: # -1 表示找不到路径，直接返回-1\n",
    "                return -1\n",
    "            else:\n",
    "                res+=tmp\n",
    "            prex, prey = sx, sy\n",
    "            \n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def cutOffTree(self, forest: List[List[int]]) -> int:\n",
    "        m, n = len(forest), len(forest[0])\n",
    "        queue = [(forest[i][j], i, j) for i in range(m) for j in range(n) if forest[i][j] > 1]\n",
    "        heapify(queue)\n",
    "\n",
    "        def bfs(sx, sy, ex, ey):\n",
    "            dx = [1, -1, 0, 0]\n",
    "            dy = [0, 0, 1, -1]\n",
    "            visit = [[True] * n for _ in range(m)]\n",
    "            steps = 0\n",
    "            queue = [(sx, sy)]\n",
    "            visit[sx][sy] = False\n",
    "            while queue:\n",
    "                next_queue = []\n",
    "                for i, j in queue:\n",
    "                    if i == ex and j == ey:\n",
    "                        return steps\n",
    "                    for k in range(4):\n",
    "                        x, y = i + dx[k], j + dy[k]\n",
    "                        if 0 <= x < m and 0 <= y < n:\n",
    "                            if visit[x][y] and forest[x][y] > 0:\n",
    "                                next_queue.append((x, y))\n",
    "                                visit[x][y] = False\n",
    "                queue = next_queue\n",
    "                steps += 1\n",
    "            return -1\n",
    "\n",
    "        ans = 0\n",
    "        sx, sy = 0, 0\n",
    "        while queue:\n",
    "            _, ex, ey = heappop(queue)\n",
    "            steps = bfs(sx, sy, ex, ey)\n",
    "            if steps >= 0:\n",
    "                ans += steps\n",
    "            else:\n",
    "                return -1\n",
    "            sx, sy = ex, ey\n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def cutOffTree(self, forest: List[List[int]]) -> int:\n",
    "        def bfs(sx: int, sy: int, tx: int, ty: int)->int:\n",
    "            m,n = len(forest), len(forest[0])\n",
    "            q = deque([(0, sx, sy)])\n",
    "            vis = {(sx, sy)}\n",
    "            while q:\n",
    "                d, x, y = q.popleft()\n",
    "                if x == tx and y == ty:\n",
    "                    return d \n",
    "                for nx, ny in ((x - 1, y), (x + 1, y), (x, y - 1), (x, y + 1)):\n",
    "                    if 0 <= nx < m and 0 <= ny < n and forest[nx][ny] and (nx, ny) not in vis:\n",
    "                        vis.add((nx, ny))\n",
    "                        q.append((d + 1, nx, ny))\n",
    "            return -1\n",
    "        \n",
    "        trees = sorted((h, i, j) for i, row in enumerate(forest) for j, h in enumerate(row) if h > 1)\n",
    "        ans = preI = preJ = 0\n",
    "        for _, i, j in trees:\n",
    "            d = bfs(preI,preJ,i, j)\n",
    "            if d < 0:\n",
    "                return -1\n",
    "            ans += d \n",
    "            preI,preJ = i, j \n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def cutOffTree(self, forest: List[List[int]]) -> int:\n",
    "        m,n=len(forest),len(forest[0])\n",
    "        s=[]\n",
    "        for i in range(m):\n",
    "            for j in range(n):\n",
    "                if forest[i][j]>1:\n",
    "                    s.append((forest[i][j],i,j))\n",
    "        s.sort(key=lambda x: x[0])\n",
    "        # print(\"for\",forest)\n",
    "        # print(\"s\",s)\n",
    "        def dis(x1,y1,x2,y2):\n",
    "            if x1==x2 and y1==y2: return 0\n",
    "            di=[(0,1),(0,-1),(-1,0),(1,0)]\n",
    "            step=0\n",
    "            q=[(x1,y1)]\n",
    "            s=[[False for _ in range(n)] for _ in range(m)]\n",
    "            while len(q)>0:\n",
    "                size=len(q)\n",
    "                while (size>0):\n",
    "                    c=q[0]\n",
    "                    # print(c)\n",
    "                    s[c[0]][c[1]]=True\n",
    "                    for _ in di:\n",
    "                        nx, ny = c[0]+_[0], c[1]+_[1]\n",
    "                        if 0<=nx<m and 0<=ny<n and forest[nx][ny]>0 and s[nx][ny] is False:\n",
    "                            if nx==x2 and ny==y2: return step+1\n",
    "                            q.append((nx,ny))\n",
    "                            s[nx][ny]=True      \n",
    "                    q.pop(0)\n",
    "                    size-=1\n",
    "                step+=1\n",
    "            return -1\n",
    "            \n",
    "        res=dis(0,0,s[0][1], s[0][2])\n",
    "        # print(res)\n",
    "        for i in range(len(s)-1):\n",
    "            add=dis(s[i][1], s[i][2], s[i+1][1], s[i+1][2])\n",
    "            # print(add)\n",
    "            if add==-1: return -1\n",
    "            res+=add\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def cutOffTree(self, forest: List[List[int]]) -> int:\n",
    "        m,n=len(forest),len(forest[0])\n",
    "        s=[]\n",
    "        for i in range(m):\n",
    "            for j in range(n):\n",
    "                if forest[i][j]>1:\n",
    "                    s.append((forest[i][j],i,j))\n",
    "        s.sort(key=lambda x: x[0])\n",
    "        # print(\"for\",forest)\n",
    "        # print(\"s\",s)\n",
    "        def dis(x1,y1,x2,y2):\n",
    "            if x1==x2 and y1==y2: return 0\n",
    "            di=[(0,1),(0,-1),(-1,0),(1,0)]\n",
    "            step=0\n",
    "            q=[(x1,y1)]\n",
    "            s=[[False for _ in range(n)] for _ in range(m)]\n",
    "            while len(q)>0:\n",
    "                size=len(q)\n",
    "                while (size>0):\n",
    "                    c=q[0]\n",
    "                    # print(c)\n",
    "                    s[c[0]][c[1]]=True\n",
    "                    for _ in di:\n",
    "                        nx, ny = c[0]+_[0], c[1]+_[1]\n",
    "                        if 0<=nx<m and 0<=ny<n and forest[nx][ny]>0 and s[nx][ny] is False:\n",
    "                            if nx==x2 and ny==y2: return step+1\n",
    "                            q.append((nx,ny))\n",
    "                            s[nx][ny]=True      \n",
    "                    q.pop(0)\n",
    "                    size-=1\n",
    "                step+=1\n",
    "            return -1\n",
    "            \n",
    "        res=dis(0,0,s[0][1], s[0][2])\n",
    "        # print(res)\n",
    "        for i in range(len(s)-1):\n",
    "            add=dis(s[i][1], s[i][2], s[i+1][1], s[i+1][2])\n",
    "            # print(add)\n",
    "            if add==-1: return -1\n",
    "            res+=add\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    \n",
    "    def cutOffTree(self, forest):\n",
    "        res = 0\n",
    "        fangxiangs=[[-1,0],[1,0],[0,1],[0,-1]]\n",
    "        w = len(forest[0]) # 获取有多少列\n",
    "        h = len(forest) #获取有多少行\n",
    "        tree = [ [forest[x][y],x,y] for x in range(h) for y in range(w) if forest[x][y]>1 ]\n",
    "        # 生成要砍的树\n",
    "        tree = sorted(tree, key=lambda x: x[0] ) # 对要砍的树进行排序\n",
    "        \n",
    "        def PintA2PointB_bushu(forest, diana,dianb):\n",
    "            if diana==dianb : return 0\n",
    "            jieguo=-1\n",
    "\n",
    "            flag=[ [0]*len(forest[0]) for _ in range(len(forest)) ]\n",
    "        \n",
    "            duilie = []\n",
    "            \n",
    "            duilie.append(diana)\n",
    "            flag[diana[0]][diana[1]]=1\n",
    "            \n",
    "            while duilie:\n",
    "                jieguo+=1\n",
    "                for _ in range(len(duilie)):\n",
    "                    \n",
    "                    duishou = duilie.pop(0)\n",
    "                    if duishou==dianb:\n",
    "                        return jieguo\n",
    "                    \n",
    "                    for fangxiang in fangxiangs:\n",
    "                        \n",
    "                        next_i,next_j = duishou[0]+fangxiang[0],duishou[1]+fangxiang[1]\n",
    "                        \n",
    "                        if 0<= next_i < h and 0<= next_j<w:\n",
    "                            \n",
    "                            if flag[next_i][next_j]==0 and forest[next_i][next_j]>0:\n",
    "                                \n",
    "                                duilie.append([next_i, next_j])\n",
    "                                \n",
    "                                flag[next_i][next_j]=1\n",
    "\n",
    "            return -1\n",
    "        res+=PintA2PointB_bushu(forest,[0,0],[tree[0][1],tree[0][2]])\n",
    "        for i in range(len(tree)-1):\n",
    "            tem = PintA2PointB_bushu(forest,tree[i][1:],tree[i+1][1:])\n",
    "            if tem == -1:\n",
    "                return -1\n",
    "            res+=tem\n",
    "        # print(res)\n",
    "        \n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "'''\n",
    "1.能否不经过其他树，直接走到最小的树\n",
    "2.从最小的树出发能否走到\n",
    "'''\n",
    "class Solution:\n",
    "    def cutOffTree(self, forest: List[List[int]]) -> int:\n",
    "        m = len(forest)\n",
    "        n = len(forest[0])\n",
    "        steps = [(-1, 0), (0, -1), (1, 0), (0, 1)]\n",
    "\n",
    "        nums = list(x for nums in forest for x in nums if x != 1 and x != 0)\n",
    "        nums.sort()\n",
    "\n",
    "        index = dict()\n",
    "        for i in range(m):\n",
    "            for j in range(n):\n",
    "                if forest[i][j] != 0 and forest[i][j] != 1:\n",
    "                    index[forest[i][j]] = (i, j)\n",
    "        #print(index)\n",
    "        #曼哈顿距离\n",
    "        def dis(x, y):\n",
    "            return abs(x[0] - y[0]) + abs(x[1] - y[1])\n",
    "\n",
    "        def A_star(cur, tar):\n",
    "\n",
    "            from_a = dict()\n",
    "            from_a[cur] = 0\n",
    "\n",
    "            q = [(0, cur)]\n",
    "\n",
    "            while q:\n",
    "                _, x = heapq.heappop(q)\n",
    "                a_to_x = from_a[x]\n",
    "                for (xx, yy) in steps:\n",
    "                    new_x = x[0] + xx\n",
    "                    new_y = x[1] + yy\n",
    "                    if 0 <= new_x < m and 0 <= new_y < n and forest[new_x][new_y]:\n",
    "                        if (new_x, new_y) not in from_a or a_to_x + 1 < from_a[(new_x, new_y)]: \n",
    "                            new_x_to_b = dis((new_x, new_y), tar) \n",
    "                            heapq.heappush(q, (a_to_x + 1 + new_x_to_b, (new_x, new_y)))\n",
    "                            from_a[(new_x, new_y)] = a_to_x + 1\n",
    "\n",
    "                if tar in from_a:\n",
    "                    return from_a[tar]\n",
    "            return -1\n",
    "\n",
    "                \n",
    "        if forest[0][0] == 0:\n",
    "            return -1\n",
    "        pre = (0, 0)    \n",
    "        ans = 0\n",
    "        for num in nums:\n",
    "            cur = index[num]\n",
    "            d = A_star(pre, cur)\n",
    "            if d == -1:\n",
    "                return -1\n",
    "            ans += d\n",
    "            pre = cur\n",
    "              \n",
    "        return ans\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from collections import deque\n",
    "import heapq\n",
    "class Solution:\n",
    "    def cutOffTree(self, forest: List[List[int]]) -> int:\n",
    "        m = len(forest)\n",
    "        n = len(forest[0])\n",
    "        hp = []\n",
    "        def bfs(cur, tar):\n",
    "            se = {cur}\n",
    "            que = deque([[cur, 0]])\n",
    "            stp = 0\n",
    "            if forest[cur[0]][cur[1]] == tar:\n",
    "                return stp, cur\n",
    "            while que:\n",
    "                current, stp = que.popleft()\n",
    "                for nxti, nxtj in [(current[0]-1, current[1]), (current[0]+1, current[1]), (current[0], current[1]-1), (current[0], current[1]+1)]:\n",
    "                    if 0 <= nxti < m and 0 <= nxtj < n and (nxti, nxtj) not in se and forest[nxti][nxtj] != 0:\n",
    "                        se.add((nxti, nxtj))\n",
    "                        if forest[nxti][nxtj] == tar:\n",
    "                            return stp+1, (nxti, nxtj)\n",
    "                        else:\n",
    "                            que.append([(nxti, nxtj), stp+1])\n",
    "            return None, None\n",
    "\n",
    "        for i in range(m):\n",
    "            for j in range(n):\n",
    "                if forest[i][j] >= 2:\n",
    "                    heapq.heappush(hp, forest[i][j])\n",
    "        \n",
    "        cur = (0, 0)\n",
    "        if forest[0][0] == 0:\n",
    "            return -1\n",
    "        ans = 0\n",
    "        while hp:\n",
    "            tar = heapq.heappop(hp)\n",
    "            temp, cur = bfs(cur, tar)\n",
    "            if not cur:\n",
    "                return -1\n",
    "            ans += temp\n",
    "        return ans\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def cutOffTree(self, forest: List[List[int]]) -> int:\n",
    "\n",
    "        def bfs(sx: int, sy: int, tx: int, ty: int) -> int:\n",
    "            m, n = len(forest), len(forest[0])\n",
    "            q = deque([(0, sx, sy)])\n",
    "            vis = {(sx, sy)}\n",
    "            while q:\n",
    "                d, x, y = q.popleft()\n",
    "                if x == tx and y == ty:\n",
    "                    return d\n",
    "                for nx, ny in ((x - 1, y), (x + 1, y), (x, y - 1), (x, y + 1)):\n",
    "                    if 0 <= nx < m and 0 <= ny < n and forest[nx][ny] and (nx, ny) not in vis:\n",
    "                        vis.add((nx, ny))\n",
    "                        q.append((d + 1, nx, ny))\n",
    "            return -1\n",
    "\n",
    "        trees = sorted((h, i, j) for i, row in enumerate(forest) for j, h in enumerate(row) if h > 1)\n",
    "        ans = preI = preJ = 0\n",
    "        for _, i, j in trees:\n",
    "            d = bfs(preI, preJ, i, j)\n",
    "            if d < 0:\n",
    "                return -1\n",
    "            ans += d\n",
    "            preI, preJ = i, j\n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def cutOffTree(self, forest: List[List[int]]) -> int:\n",
    "        m, n = len(forest), len(forest[0])\n",
    "        queue = [(forest[i][j], i, j) for i in range(m) for j in range(n) if forest[i][j] > 1]\n",
    "        queue.sort(reverse=True)\n",
    "\n",
    "        def bfs(sx, sy, ex, ey):\n",
    "            dx = [1, -1, 0, 0]\n",
    "            dy = [0, 0, 1, -1]\n",
    "            visit = [[True] * n for _ in range(m)]\n",
    "            steps = 0\n",
    "            queue = [(sx, sy)]\n",
    "            visit[sx][sy] = False\n",
    "            while queue:\n",
    "                next_queue = []\n",
    "                for i, j in queue:\n",
    "                    if i == ex and j == ey:\n",
    "                        return steps\n",
    "                    for k in range(4):\n",
    "                        x, y = i + dx[k], j + dy[k]\n",
    "                        if 0 <= x < m and 0 <= y < n:\n",
    "                            if visit[x][y] and forest[x][y] > 0:\n",
    "                                next_queue.append((x, y))\n",
    "                                visit[x][y] = False\n",
    "                queue = next_queue\n",
    "                steps += 1\n",
    "            return -1\n",
    "\n",
    "        ans = 0\n",
    "        sx, sy = 0, 0\n",
    "        while queue:\n",
    "            _, ex, ey = queue.pop()\n",
    "            steps = bfs(sx, sy, ex, ey)\n",
    "            if steps >= 0:\n",
    "                ans += steps\n",
    "            else:\n",
    "                return -1\n",
    "            sx, sy = ex, ey\n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "'''\n",
    "1.能否不经过其他树，直接走到最小的树\n",
    "2.从最小的树出发能否走到\n",
    "'''\n",
    "class Solution:\n",
    "    def cutOffTree(self, forest: List[List[int]]) -> int:\n",
    "        m = len(forest)\n",
    "        n = len(forest[0])\n",
    "        steps = [(-1, 0), (1, 0), (0, -1), (0, 1)]\n",
    "\n",
    "        nums = list(x for nums in forest for x in nums if x != 1 and x != 0)\n",
    "        nums.sort()\n",
    "        #print(nums)\n",
    "\n",
    "        index = dict()\n",
    "        for i in range(m):\n",
    "            for j in range(n):\n",
    "                if forest[i][j] not in [0, 1]:\n",
    "                    index[forest[i][j]] = (i, j)\n",
    "        #print(index)\n",
    "        #曼哈顿距离\n",
    "        def dis(x, y):\n",
    "            return abs(x[0] - y[0]) + abs(x[1] - y[1])\n",
    "\n",
    "        def A_star(cur, tar):\n",
    "            #print(cur, tar)\n",
    "            from_a = dict()\n",
    "            from_a[cur] = 0\n",
    "\n",
    "            q = [(0, cur)]\n",
    "\n",
    "            while q:\n",
    "                _, x = heapq.heappop(q)\n",
    "                a_to_x = from_a[x]\n",
    "                for (xx, yy) in steps:\n",
    "                    new_x = x[0] + xx\n",
    "                    new_y = x[1] + yy\n",
    "                    if 0 <= new_x < m and 0 <= new_y < n and forest[new_x][new_y]:\n",
    "                        if (new_x, new_y) not in from_a or a_to_x + 1 < from_a[(new_x, new_y)]: \n",
    "                            new_x_to_b = dis((new_x, new_y), tar) \n",
    "                            heapq.heappush(q, (a_to_x + 1 + new_x_to_b, (new_x, new_y)))\n",
    "                            from_a[(new_x, new_y)] = a_to_x + 1\n",
    "\n",
    "                if tar in from_a:\n",
    "                    return from_a[tar]\n",
    "            return -1\n",
    "\n",
    "                \n",
    "        if forest[0][0] == 0:\n",
    "            return -1\n",
    "        pre = (0, 0)    \n",
    "        ans = 0\n",
    "        #cnt = 0\n",
    "        for num in nums:\n",
    "            cur = index[num]\n",
    "            d = A_star(pre, cur)\n",
    "            if d == -1:\n",
    "                return -1\n",
    "            ans += d\n",
    "            pre = cur\n",
    "            #cnt += 1\n",
    "            #print(cnt)    \n",
    "        return ans\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from sortedcontainers import SortedList \n",
    "class Solution:\n",
    "    def cutOffTree(self, forest: List[List[int]]) -> int:\n",
    "        m,n = len(forest), len(forest[0]) \n",
    "        sl = []\n",
    "        for i in range(m):\n",
    "            for j in range(n):\n",
    "                if forest[i][j] > 1:\n",
    "                    sl.append((forest[i][j], i, j)) \n",
    "        def bfs(sx, sy, tx, ty):\n",
    "            Q=deque([(0, sx,sy)])\n",
    "            vis = [[0] * n for _ in range(m)]\n",
    "            vis[sx][sy]= 1\n",
    "            while Q:\n",
    "                d, x, y = Q.popleft() \n",
    "                if (x, y) == (tx,ty):\n",
    "                    return d \n",
    "                for [nx, ny] in [[x+1,y], [x-1,y], [x,y+1],[x,y-1]]:\n",
    "                    if 0<=nx<m and 0<=ny<n and forest[nx][ny] > 0 and not vis[nx][ny]:\n",
    "                        vis[nx][ny] = 1\n",
    "                        Q.append((d+1, nx, ny))\n",
    "            return -1 \n",
    "\n",
    "        pre = (0, 0)\n",
    "        ans = 0\n",
    "        for k, x, y in sorted(sl):\n",
    "            \n",
    "            d = bfs(pre[0], pre[1], x, y)\n",
    "            #print(k, x, y, d)\n",
    "            if d == -1:\n",
    "                return -1 \n",
    "            ans += d \n",
    "            pre = (x, y)\n",
    "        #print(len(sl))\n",
    "        return ans "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def cutOffTree(self, forest: List[List[int]]) -> int:\n",
    "        w = len(forest[0]) # 获取有多少列\n",
    "        h = len(forest) #获取有多少行\n",
    "        direction = [ [0,1],[0,-1],[1,0],[-1,0] ] # 每一步走的方向\n",
    "        tree = [ [forest[x][y],x,y] for x in range(h) for y in range(w) if forest[x][y]>1 ]\n",
    "        # 生成要砍的树\n",
    "        tree = sorted(tree, key=lambda x: x[0] ) # 对要砍的树进行排序\n",
    "        def helper(val,sx,sy): # bfs搜素函数，返回(sx,sy)为起点，砍高为val树的最短路径\n",
    "            res = -1\n",
    "            visited = [ [0]*w for _ in range(h) ]\n",
    "            quque = [ (sx,sy)]\n",
    "            while quque:\n",
    "                res+=1\n",
    "                for _ in range(len(quque)):\n",
    "                    x, y = quque[0]\n",
    "                    quque.pop(0)\n",
    "                    if forest[x][y]==val:\n",
    "                        forest[x][y]=1\n",
    "                        return res\n",
    "                    for i in range(4):\n",
    "                        dx, dy = direction[i]\n",
    "                        x1,y1 = x+dx, y+dy\n",
    "                        if 0<=x1<h and 0<=y1<w : # 边界条件\n",
    "                            if (not visited[x1][y1]) and forest[x1][y1]>0:#只能访问没被访问过的，以及不能是0\n",
    "                                quque.append((x1,y1)) # 入队\n",
    "                                visited[x1][y1]=1 # 设置为访问过\n",
    "            return -1\n",
    "        re = 0\n",
    "        prex, prey=0, 0\n",
    "        for t in tree:\n",
    "            val,sx,sy = t\n",
    "            tmp = helper(val,prex,prey)\n",
    "            if tmp==-1: # -1 表示找不到路径，直接返回-1\n",
    "                return -1\n",
    "            else:\n",
    "                re+=tmp\n",
    "            prex, prey = sx, sy\n",
    "        return re\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def cutOffTree(self, forest: List[List[int]]) -> int:\n",
    "        m, n = len(forest), len(forest[0])\n",
    "\n",
    "        def distance(x1, y1, x2, y2):\n",
    "            todo = [(0, x1 , y1)]\n",
    "            visited = {(x1,y1)}\n",
    "            while todo:\n",
    "                step, x, y = todo.pop(0)\n",
    "                if x == x2 and y == y2: return step\n",
    "                for _x, _y in [(0,1),(0,-1),(-1,0),(1,0)]:\n",
    "                    if 0 <= x+_x < m and 0 <= y+_y < n and forest[x+_x][y+_y]>0 and (x+_x,y+_y) not in visited: \n",
    "                        todo.append((step+1, x+_x,y+_y))\n",
    "                        visited.add((x+_x,y+_y))\n",
    "\n",
    "            return -1\n",
    "\n",
    "        trees = sorted((h, i, j) for i, row in enumerate(forest) for j, h in enumerate(row) if h > 1)\n",
    "        step = 0\n",
    "        bx, by = 0, 0\n",
    "        while trees:\n",
    "            _, ex, ey = trees.pop(0)\n",
    "            dis = distance(bx, by, ex, ey)\n",
    "            if dis < 0:\n",
    "                return -1\n",
    "            step += dis\n",
    "            bx, by = ex, ey\n",
    "        \n",
    "        return step"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def cutOffTree(self, forest: List[List[int]]) -> int:\n",
    "        m=len(forest)\n",
    "        n=len(forest[0])\n",
    "        arr=[]\n",
    "        for i in range(m):\n",
    "            for j in range(n):\n",
    "                if forest[i][j]>1:\n",
    "                    arr.append(forest[i][j])\n",
    "        arr.sort()\n",
    "        ans=0\n",
    "        def dfs(i,j,t):\n",
    "            stack=collections.deque()\n",
    "            stack.append([i,j,0])\n",
    "            vis=set()\n",
    "            while stack:\n",
    "                x,y,d=stack.popleft()\n",
    "                if forest[x][y]==t:\n",
    "                    return x,y,d\n",
    "                if (x,y) in vis:\n",
    "                    continue\n",
    "                vis.add((x,y))\n",
    "                for x1,y1 in [[x+1,y],[x-1,y],[x,y+1],[x,y-1]]:\n",
    "                    if 0<=x1<m and 0<=y1<n and (x1,y1) not in vis and forest[x1][y1]!=0:\n",
    "                        stack.append([x1,y1,d+1])\n",
    "            \n",
    "            return -1,-1,-1\n",
    "        sx,sy=0,0\n",
    "\n",
    "        for t in arr:\n",
    "            nx,ny,d=dfs(sx,sy,t)\n",
    "            if d==-1:\n",
    "                return -1\n",
    "            else:\n",
    "                ans+=d\n",
    "                sx=nx\n",
    "                sy=ny \n",
    "        return ans \n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def cutOffTree(self, forest: List[List[int]]) -> int:\n",
    "        M = len(forest)\n",
    "        N = len(forest[0])\n",
    "        trees = []\n",
    "        for i in range(M):\n",
    "            for j in range(N):\n",
    "                if (forest[i][j] > 1):\n",
    "                    trees.append((forest[i][j], i, j))\n",
    "        trees.sort()\n",
    "        preX, preY = 0, 0\n",
    "        res = 0\n",
    "        for height, curX, curY in trees:\n",
    "            steps = self.bfs(forest, preX, preY, curX, curY)\n",
    "            if steps == -1:\n",
    "                return -1\n",
    "            res += steps\n",
    "            preX, preY = curX, curY\n",
    "        return res\n",
    "    \n",
    "    def bfs(self, forest, startX, startY, targetX, targetY):\n",
    "        M = len(forest)\n",
    "        N = len(forest[0])\n",
    "        dirs = [(0, 1), (0, -1), (-1, 0), (1, 0)]\n",
    "        steps = 0\n",
    "        queue = collections.deque()\n",
    "        queue.append((startX, startY))\n",
    "        visited = set()\n",
    "        visited.add((startX, startY))\n",
    "        while queue:\n",
    "            size = len(queue)\n",
    "            for _ in range(size):\n",
    "                curX, curY = queue.popleft()\n",
    "                if curX == targetX and curY == targetY:\n",
    "                    return steps\n",
    "                for d in dirs:\n",
    "                    nX = curX + d[0]\n",
    "                    nY = curY + d[1]\n",
    "                    if 0 <= nX < M and 0 <= nY < N and forest[nX][nY] != 0 and ((nX, nY) not in visited):\n",
    "                        queue.append((nX, nY))\n",
    "                        visited.add((nX, nY))\n",
    "            steps += 1\n",
    "        return -1\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def cutOffTree(self, forest: List[List[int]]) -> int:\n",
    "        m,n = len(forest),len(forest[0])\n",
    "\n",
    "        def cal(x1,y1,x2,y2):\n",
    "            q = deque([(0,x1,y1)])\n",
    "            visited = {(x1,y1)}\n",
    "            while q:\n",
    "                step,i,j = q.popleft()\n",
    "                if i==x2 and j==y2:\n",
    "                    return step\n",
    "                for ii,jj in ((i+1,j),(i-1,j),(i,j+1),(i,j-1)):\n",
    "                    if 0<=ii<m and 0<=jj<n and forest[ii][jj]>0 and (ii,jj) not in visited:\n",
    "                        visited.add((ii,jj))\n",
    "                        q.append((step+1,ii,jj))\n",
    "            return -1\n",
    "\n",
    "        q = []\n",
    "        for i in range(m):\n",
    "            for j in range(n):\n",
    "                if forest[i][j]>1:\n",
    "                    q.append((forest[i][j],i,j))\n",
    "        q.sort()\n",
    "        \n",
    "        x,y = 0,0\n",
    "\n",
    "        res = 0\n",
    "\n",
    "        for _,i,j in q:\n",
    "            tmp = cal(x,y,i,j)\n",
    "            if tmp<0:\n",
    "                return -1\n",
    "            res+=tmp\n",
    "            x,y = i,j \n",
    "        \n",
    "        return res\n",
    "\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from sortedcontainers import SortedList \n",
    "class Solution:\n",
    "    def cutOffTree(self, forest: List[List[int]]) -> int:\n",
    "        m,n = len(forest), len(forest[0]) \n",
    "        sl = SortedList()\n",
    "        for i in range(m):\n",
    "            for j in range(n):\n",
    "                if forest[i][j] > 1:\n",
    "                    sl.add((forest[i][j], i, j)) \n",
    "        def bfs(sx, sy, tx, ty):\n",
    "            Q=deque([(0, sx,sy)])\n",
    "            vis = [[0] * n for _ in range(m)]\n",
    "            vis[sx][sy]= 1\n",
    "            while Q:\n",
    "                d, x, y = Q.popleft() \n",
    "                if (x, y) == (tx,ty):\n",
    "                    return d \n",
    "                for [nx, ny] in [[x+1,y], [x-1,y], [x,y+1],[x,y-1]]:\n",
    "                    if 0<=nx<m and 0<=ny<n and forest[nx][ny] > 0 and not vis[nx][ny]:\n",
    "                        vis[nx][ny] = 1\n",
    "                        Q.append((d+1, nx, ny))\n",
    "            return -1 \n",
    "\n",
    "        pre = (0, 0)\n",
    "        ans = 0\n",
    "        for k, x, y in sl:\n",
    "            \n",
    "            d = bfs(pre[0], pre[1], x, y)\n",
    "            #print(k, x, y, d)\n",
    "            if d == -1:\n",
    "                return -1 \n",
    "            ans += d \n",
    "            pre = (x, y)\n",
    "        #print(len(sl))\n",
    "        return ans "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from collections import deque\n",
    "class Solution:\n",
    "    def cutOffTree(self, forest: List[List[int]]) -> int:\n",
    "        dirs = [(-1, 0), (1, 0), (0, 1), (0, -1)]\n",
    "        m, n = len(forest), len(forest[0])\n",
    "        # init trees, (x, y) sorted in forest[x][y] order\n",
    "        trees = []\n",
    "        for x in range(m):\n",
    "            for y in range(n):\n",
    "                if forest[x][y] > 1:\n",
    "                    trees.append((x, y))\n",
    "        trees.sort(key=lambda tree:forest[tree[0]][tree[1]])\n",
    "        # returns dist between src and dest\n",
    "        def bfs(src: tuple, dest: tuple) -> int:\n",
    "            queue = deque([src])\n",
    "            vis = set([(src)])\n",
    "            step = 0\n",
    "            while queue:\n",
    "                size = len(queue)\n",
    "                for _ in range(size):\n",
    "                    x, y = queue.popleft()\n",
    "                    if (x, y) == dest:\n",
    "                        return step\n",
    "                    for dx, dy in dirs:\n",
    "                        nx, ny = x + dx, y + dy\n",
    "                        if 0 <= nx < m and 0 <= ny < n and (nx, ny) not in vis and forest[nx][ny] != 0:\n",
    "                            queue.append((nx, ny))\n",
    "                            vis.add((nx, ny))\n",
    "                step += 1\n",
    "            return -1\n",
    "        # the total dist between each next taller trees, starting from (0, 0)\n",
    "        res = 0\n",
    "        src = (0, 0)\n",
    "        for i in range(len(trees)):\n",
    "            dest = trees[i]\n",
    "            dist = bfs(src, dest)\n",
    "            if dist == -1: return -1\n",
    "            res += dist\n",
    "            src = dest\n",
    "        return res\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "import collections\n",
    "class Solution:\n",
    "    def cutOffTree(self, forest: List[List[int]]) -> int:\n",
    "        M = len(forest)\n",
    "        N = len(forest[0])\n",
    "        trees = []\n",
    "        for i in range(M):\n",
    "            for j in range(N):\n",
    "                if (forest[i][j] > 1):\n",
    "                    trees.append((forest[i][j], i, j))\n",
    "        trees.sort()\n",
    "        preX, preY = 0, 0\n",
    "        res = 0\n",
    "        for height, curX, curY in trees:\n",
    "            steps = self.bfs(forest, preX, preY, curX, curY)\n",
    "            if steps == -1:\n",
    "                return -1\n",
    "            res += steps\n",
    "            preX, preY = curX, curY\n",
    "        return res\n",
    "    \n",
    "    def bfs(self, forest, startX, startY, targetX, targetY):\n",
    "        M = len(forest)\n",
    "        N = len(forest[0])\n",
    "        dirs = [(0, 1), (0, -1), (-1, 0), (1, 0)]\n",
    "        steps = 0\n",
    "        queue = collections.deque()\n",
    "        queue.append((startX, startY))\n",
    "        visited = set()\n",
    "        visited.add((startX, startY))\n",
    "        while queue:\n",
    "            size = len(queue)\n",
    "            for _ in range(size):\n",
    "                curX, curY = queue.popleft()\n",
    "                if curX == targetX and curY == targetY:\n",
    "                    return steps\n",
    "                for d in dirs:\n",
    "                    nX = curX + d[0]\n",
    "                    nY = curY + d[1]\n",
    "                    if 0 <= nX < M and 0 <= nY < N and forest[nX][nY] != 0 and ((nX, nY) not in visited):\n",
    "                        queue.append((nX, nY))\n",
    "                        visited.add((nX, nY))\n",
    "            steps += 1\n",
    "        return -1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from sortedcontainers import SortedList \n",
    "class Solution:\n",
    "    def cutOffTree(self, forest: List[List[int]]) -> int:\n",
    "        m,n = len(forest), len(forest[0]) \n",
    "        sl = []\n",
    "        for i in range(m):\n",
    "            for j in range(n):\n",
    "                if forest[i][j] > 1:\n",
    "                    sl.append((forest[i][j], i, j)) \n",
    "        def bfs(sx, sy, tx, ty):\n",
    "            Q=deque([(0, sx,sy)])\n",
    "            vis = [[0] * n for _ in range(m)]\n",
    "            vis[sx][sy]= 1\n",
    "            while Q:\n",
    "                d, x, y = Q.popleft() \n",
    "                if (x, y) == (tx,ty):\n",
    "                    return d \n",
    "                for [nx, ny] in [[x+1,y], [x-1,y], [x,y+1],[x,y-1]]:\n",
    "                    if 0<=nx<m and 0<=ny<n and forest[nx][ny] > 0 and not vis[nx][ny]:\n",
    "                        vis[nx][ny] = 1\n",
    "                        Q.append((d+1, nx, ny))\n",
    "            return -1 \n",
    "\n",
    "        pre = (0, 0)\n",
    "        ans = 0\n",
    "        sl.sort() \n",
    "        for k, x, y in sl:\n",
    "            d = bfs(pre[0], pre[1], x, y)\n",
    "            #print(k, x, y, d)\n",
    "            if d == -1:\n",
    "                return -1 \n",
    "            ans += d \n",
    "            pre = (x, y)\n",
    "        #print(len(sl))\n",
    "        return ans "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def cutOffTree(self, forest: List[List[int]]) -> int:\n",
    "        m=len(forest)\n",
    "        n=len(forest[0])\n",
    "        tree=[]\n",
    "        for i in range(m):\n",
    "            for j in range(n):\n",
    "                if (forest[i][j]>1):\n",
    "                    tree.append((forest[i][j],i,j))\n",
    "        tree.sort()\n",
    "        px,py=0,0\n",
    "        res=0\n",
    "        for h,cx,cy in tree:\n",
    "            steps=self.bfs(forest,px,py,cx,cy)\n",
    "            if steps==-1:\n",
    "                return -1\n",
    "            res+=steps\n",
    "            px,py=cx,cy\n",
    "        return res\n",
    "    \n",
    "    def bfs(self,forest,startx,starty,targetx,targety):\n",
    "        m=len(forest)\n",
    "        n=len(forest[0])\n",
    "        dirs=[(0,1),(0,-1),(1,0),(-1,0)]\n",
    "        steps=0\n",
    "        q=collections.deque()\n",
    "        q.append((startx,starty))\n",
    "        visited=set()\n",
    "        visited.add((startx,starty))\n",
    "        while q:\n",
    "            size=len(q)\n",
    "            for _ in range(size):\n",
    "                cx,cy=q.popleft()\n",
    "                if cx==targetx and cy==targety:\n",
    "                    return steps\n",
    "                for d in dirs:\n",
    "                    nx=cx+d[0]\n",
    "                    ny=cy+d[1]\n",
    "                    if 0<=nx<m and 0<=ny<n and forest[nx][ny]!=0 and (nx,ny) not in visited:\n",
    "                        q.append((nx,ny))\n",
    "                        visited.add((nx,ny))\n",
    "            steps+=1\n",
    "        return -1\n",
    "\n",
    "    \n",
    "\n",
    "            "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "'''\n",
    "1.能否不经过其他树，直接走到最小的树\n",
    "2.从最小的树出发能否走到\n",
    "'''\n",
    "class Solution:\n",
    "    def cutOffTree(self, forest: List[List[int]]) -> int:\n",
    "        m = len(forest)\n",
    "        n = len(forest[0])\n",
    "        steps = [(-1, 0), (0, -1), (1, 0), (0, 1)]\n",
    "\n",
    "        nums = list(x for nums in forest for x in nums if x != 1 and x != 0)\n",
    "        nums.sort()\n",
    "        #print(nums)\n",
    "\n",
    "        index = dict()\n",
    "        for i in range(m):\n",
    "            for j in range(n):\n",
    "                if forest[i][j] not in [0, 1]:\n",
    "                    index[forest[i][j]] = (i, j)\n",
    "        #print(index)\n",
    "        #曼哈顿距离\n",
    "        def dis(x, y):\n",
    "            return abs(x[0] - y[0]) + abs(x[1] - y[1])\n",
    "\n",
    "        def A_star(cur, tar):\n",
    "\n",
    "            from_a = dict()\n",
    "            from_a[cur] = 0\n",
    "\n",
    "            q = [(0, cur)]\n",
    "\n",
    "            while q:\n",
    "                _, x = heapq.heappop(q)\n",
    "                a_to_x = from_a[x]\n",
    "                for (xx, yy) in steps:\n",
    "                    new_x = x[0] + xx\n",
    "                    new_y = x[1] + yy\n",
    "                    if 0 <= new_x < m and 0 <= new_y < n and forest[new_x][new_y]:\n",
    "                        if (new_x, new_y) not in from_a or a_to_x + 1 < from_a[(new_x, new_y)]: \n",
    "                            new_x_to_b = dis((new_x, new_y), tar) \n",
    "                            heapq.heappush(q, (a_to_x + 1 + new_x_to_b, (new_x, new_y)))\n",
    "                            from_a[(new_x, new_y)] = a_to_x + 1\n",
    "\n",
    "                if tar in from_a:\n",
    "                    return from_a[tar]\n",
    "            return -1\n",
    "\n",
    "                \n",
    "        if forest[0][0] == 0:\n",
    "            return -1\n",
    "        pre = (0, 0)    \n",
    "        ans = 0\n",
    "        #cnt = 0\n",
    "        for num in nums:\n",
    "            cur = index[num]\n",
    "            d = A_star(pre, cur)\n",
    "            if d == -1:\n",
    "                return -1\n",
    "            ans += d\n",
    "            pre = cur\n",
    "            #cnt += 1\n",
    "            #print(cnt)    \n",
    "        return ans\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def cutOffTree(self, forest: list[list[int]]) -> int:\n",
    "        def bfs(sx: int, sy: int, tx: int, ty: int) -> int:\n",
    "            m, n = len(forest), len(forest[0])\n",
    "            q = deque([(0, sx, sy)])\n",
    "            vis = {(sx, sy)}\n",
    "            while q:\n",
    "                d, x, y = q.popleft()\n",
    "                if x == tx and y == ty:\n",
    "                    return d\n",
    "                for nx, ny in ((x - 1, y), (x + 1, y), (x, y - 1), (x, y + 1)):\n",
    "                    if (\n",
    "                        0 <= nx < m\n",
    "                        and 0 <= ny < n\n",
    "                        and forest[nx][ny]\n",
    "                        and (nx, ny) not in vis\n",
    "                    ):\n",
    "                        vis.add((nx, ny))\n",
    "                        q.append((d + 1, nx, ny))\n",
    "            return -1\n",
    "\n",
    "        trees = sorted(\n",
    "            (h, i, j)\n",
    "            for i, row in enumerate(forest)\n",
    "            for j, h in enumerate(row)\n",
    "            if h > 1\n",
    "        )\n",
    "        ans = preI = preJ = 0\n",
    "        for _, i, j in trees:\n",
    "            d = bfs(preI, preJ, i, j)\n",
    "            if d < 0:\n",
    "                return -1\n",
    "            ans += d\n",
    "            preI, preJ = i, j\n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# https://leetcode.cn/problems/cut-off-trees-for-golf-event/solutions/1512295/by-fuxuemingzhu-dtet/\n",
    "class Solution:\n",
    "    def cutOffTree(self, forest: List[List[int]]) -> int:\n",
    "        def bfs(start_x, start_y,final_x,final_y):\n",
    "\n",
    "            def insideBoard(x,y):\n",
    "                return 0 <= x < rows and 0 <= y < cols\n",
    "\n",
    "            if start_x == final_x and start_y == final_y:\n",
    "                return 0\n",
    "\n",
    "            seen = set()\n",
    "            seen.add((start_x,start_y))\n",
    "            queue = [(start_x,start_y)]\n",
    "            directions = [(1,0),(-1,0),(0,1),(0,-1)]\n",
    "            steps = 0\n",
    "            while queue:\n",
    "                n = len(queue)\n",
    "                for _ in range(n):\n",
    "                    x,y = queue.pop(0)\n",
    "                    if x == final_x and y == final_y:\n",
    "                        return steps\n",
    "                    for d in directions:\n",
    "                        nx, ny = x+d[0],y+d[1]\n",
    "                        if 0 <= nx < rows and 0 <= ny < cols and forest[nx][ny] != 0 and (nx,ny) not in seen:\n",
    "                            seen.add((nx,ny))\n",
    "                            queue.append((nx,ny))\n",
    "                steps += 1\n",
    "            return -1\n",
    "                            \n",
    "\n",
    "\n",
    "\n",
    "        rows = len(forest)\n",
    "        cols = len(forest[0])\n",
    "        trees = []\n",
    "        for i in range(rows):\n",
    "            for j in range(cols):\n",
    "                if forest[i][j] > 1:\n",
    "                    trees.append((forest[i][j],i,j))\n",
    "        trees.sort()\n",
    "\n",
    "        start_x, start_y = 0, 0\n",
    "        ans = 0\n",
    "        for height, x, y in trees:\n",
    "            distance = bfs(start_x, start_y,x,y)\n",
    "            if distance == -1:\n",
    "                return -1\n",
    "            ans += distance\n",
    "            start_x,start_y = x,y\n",
    "        return ans\n",
    "            "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "'''\n",
    "1.能否不经过其他树，直接走到最小的树\n",
    "2.从最小的树出发能否走到\n",
    "'''\n",
    "class Solution:\n",
    "    def cutOffTree(self, forest: List[List[int]]) -> int:\n",
    "        m = len(forest)\n",
    "        n = len(forest[0])\n",
    "        steps = [(-1, 0), (0, -1), (1, 0), (0, 1)]\n",
    "\n",
    "        nums = list(x for nums in forest for x in nums if x != 1 and x != 0)\n",
    "        nums.sort()\n",
    "\n",
    "        index = dict()\n",
    "        for i in range(m):\n",
    "            for j in range(n):\n",
    "                if forest[i][j] != 0 and forest[i][j] != 1:\n",
    "                    index[forest[i][j]] = (i, j)\n",
    "        #print(index)\n",
    "        #曼哈顿距离\n",
    "        def dis(x, y):\n",
    "            return abs(x[0] - y[0]) + abs(x[1] - y[1])\n",
    "\n",
    "        def A_star(cur, tar):\n",
    "\n",
    "            from_a = dict()\n",
    "            from_a[cur] = 0\n",
    "\n",
    "            q = [(0, cur[0], cur[1])]\n",
    "\n",
    "            while q:\n",
    "                _, x, y = heapq.heappop(q)\n",
    "                a_to_x = from_a[(x, y)]\n",
    "                for (xx, yy) in steps:\n",
    "                    new_x = x + xx\n",
    "                    new_y = y + yy\n",
    "                    if 0 <= new_x < m and 0 <= new_y < n and forest[new_x][new_y]:\n",
    "                        if (new_x, new_y) not in from_a or a_to_x + 1 < from_a[(new_x, new_y)]: \n",
    "                            new_x_to_b = dis((new_x, new_y), tar) \n",
    "                            heapq.heappush(q, (a_to_x + 1 + new_x_to_b, new_x, new_y))\n",
    "                            from_a[(new_x, new_y)] = a_to_x + 1\n",
    "\n",
    "                    if tar in from_a:\n",
    "                        return from_a[tar]\n",
    "            return -1\n",
    "\n",
    "        if forest[0][0] == 0:\n",
    "            return -1\n",
    "        pre = (0, 0)    \n",
    "        ans = 0\n",
    "        for num in nums:\n",
    "            cur = index[num]\n",
    "            d = A_star(pre, cur)\n",
    "            if d == -1:\n",
    "                return -1\n",
    "            ans += d\n",
    "            pre = cur\n",
    "              \n",
    "        return ans\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def cutOffTree(self, forest: List[List[int]]) -> int:\n",
    "        m, n = len(forest), len(forest[0])\n",
    "\n",
    "        def distance(x1, y1, x2, y2):\n",
    "            todo = [(0, x1 , y1)]\n",
    "            visited = {(x1,y1)}\n",
    "            while todo:\n",
    "                step, x, y = todo.pop(0)\n",
    "                if x == x2 and y == y2: return step\n",
    "                for _x, _y in [(0,1),(0,-1),(-1,0),(1,0)]:\n",
    "                    if 0 <= x+_x < m and 0 <= y+_y < n and forest[x+_x][y+_y]>0 and (x+_x,y+_y) not in visited: \n",
    "                        todo.append((step+1, x+_x,y+_y))\n",
    "                        visited.add((x+_x,y+_y))\n",
    "\n",
    "            return -1\n",
    "\n",
    "        trees = sorted((h, i, j) for i, row in enumerate(forest) for j, h in enumerate(row) if h > 1)\n",
    "        step = 0\n",
    "        bx, by = 0, 0\n",
    "        while trees:\n",
    "            _, ex, ey = heapq.heappop(trees)\n",
    "            dis = distance(bx, by, ex, ey)\n",
    "            if dis < 0:\n",
    "                return -1\n",
    "            step += dis\n",
    "            bx, by = ex, ey\n",
    "        \n",
    "        return step"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from collections import deque\n",
    "class Solution:\n",
    "    def cutOffTree(self, forest: List[List[int]]) -> int:\n",
    "        dirs = [(-1, 0), (1, 0), (0, 1), (0, -1)]\n",
    "        m, n = len(forest), len(forest[0])\n",
    "        # init trees\n",
    "        trees = []\n",
    "        for x in range(m):\n",
    "            for y in range(n):\n",
    "                if forest[x][y] > 1:\n",
    "                    trees.append((x, y))\n",
    "        trees.sort(key=lambda tree:forest[tree[0]][tree[1]])\n",
    "        \n",
    "        def bfs(src: tuple, dest: tuple) -> int:\n",
    "            queue = deque([src])\n",
    "            vis = set([(src)])\n",
    "            step = 0\n",
    "            while queue:\n",
    "                size = len(queue)\n",
    "                for _ in range(size):\n",
    "                    x, y = queue.popleft()\n",
    "                    if (x, y) == dest:\n",
    "                        return step\n",
    "                    for dx, dy in dirs:\n",
    "                        nx, ny = x + dx, y + dy\n",
    "                        if 0 <= nx < m and 0 <= ny < n and (nx, ny) not in vis and forest[nx][ny] != 0:\n",
    "                            queue.append((nx, ny))\n",
    "                            vis.add((nx, ny))\n",
    "                step += 1\n",
    "            return -1\n",
    "\n",
    "        res = 0\n",
    "        src = (0, 0)\n",
    "        for i in range(len(trees)):\n",
    "            dest = trees[i]\n",
    "            dist = bfs(src, dest)\n",
    "            if dist == -1: return -1\n",
    "            res += dist\n",
    "            src = dest\n",
    "        return res\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def BFS(self,start,end,forest):\n",
    "        visited = set()\n",
    "        visited.add((start[0],start[1]))\n",
    "        stk = [start]\n",
    "        distance = 0\n",
    "        \n",
    "        m = len(forest)\n",
    "        n = len(forest[0])\n",
    "        \n",
    "        last =start\n",
    "        while stk:\n",
    "            [x,y] = stk.pop(0)\n",
    "            if [x,y]==end:\n",
    "                return distance\n",
    "            for [nx,ny] in [[x+1,y],[x-1,y],[x,y+1],[x,y-1]]:\n",
    "                if nx<0 or ny<0 or nx>=m or ny>=n or (nx,ny) in visited or forest[nx][ny] ==0:\n",
    "                    continue\n",
    "                \n",
    "                visited.add((nx,ny))\n",
    "                stk.append([nx,ny])\n",
    "            if [x,y]==last and stk:\n",
    "                distance+=1\n",
    "                last =stk[-1]\n",
    "        return -1\n",
    "    def cutOffTree(self, forest: List[List[int]]) -> int:\n",
    "        \"\"\"假设所有树按照从高度从小到大的排序顺序为 t1,t2,t3,t4,⋯ ,tn\n",
    "        设 d(x,y) 表示从 x 到 y 之间的步数，\n",
    "        设t0为(0,0)\n",
    "        则可推出砍树的总的步数为 total=∑ d(t_i,t_i+1)(0<=i<n)\n",
    "        题目转成求两点 t_i ,t_i+1 之间的最短步数\n",
    "        \"\"\"\n",
    "        m = len(forest)\n",
    "        n = len(forest[0])\n",
    "        heights =list()\n",
    "        for i in range(m):\n",
    "            for j in range(n):\n",
    "                if forest[i][j]>1:\n",
    "                    heights.append([forest[i][j],i,j])\n",
    "        heights.sort(key = lambda x:x[0])\n",
    "        #print(heights)\n",
    "        \n",
    "        start = [0,0]\n",
    "        res = 0\n",
    "        for node in heights:\n",
    "            end = node[1:]\n",
    "            distance = self.BFS(start,end,forest)\n",
    "            start = node[1:]\n",
    "            if distance==-1:\n",
    "                return -1\n",
    "            else:\n",
    "                res+=distance\n",
    "        return res\n",
    "                \n",
    "            \n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "'''\n",
    "1.能否不经过其他树，直接走到最小的树\n",
    "2.从最小的树出发能否走到\n",
    "'''\n",
    "class Solution:\n",
    "    def cutOffTree(self, forest: List[List[int]]) -> int:\n",
    "        m = len(forest)\n",
    "        n = len(forest[0])\n",
    "        steps = [(-1, 0), (0, -1), (1, 0), (0, 1)]\n",
    "\n",
    "        nums = list(x for nums in forest for x in nums if x != 1 and x != 0)\n",
    "        nums.sort()\n",
    "\n",
    "        index = dict()\n",
    "        for i in range(m):\n",
    "            for j in range(n):\n",
    "                if forest[i][j] != 0 and forest[i][j] != 1:\n",
    "                    index[forest[i][j]] = (i, j)\n",
    "        #print(index)\n",
    "        #曼哈顿距离\n",
    "        def dis(x, y):\n",
    "            return abs(x[0] - y[0]) + abs(x[1] - y[1])\n",
    "\n",
    "        def A_star(cur, tar):\n",
    "\n",
    "            from_a = dict()\n",
    "            from_a[cur] = 0\n",
    "\n",
    "            q = [(0, cur[0], cur[1])]\n",
    "\n",
    "            while q:\n",
    "                _, x, y = heapq.heappop(q)\n",
    "                if (x, y) == tar:\n",
    "                    return from_a[tar]\n",
    "                a_to_x = from_a[(x, y)]\n",
    "                for (xx, yy) in steps:\n",
    "                    new_x = x + xx\n",
    "                    new_y = y + yy\n",
    "                    if 0 <= new_x < m and 0 <= new_y < n and forest[new_x][new_y]:\n",
    "                        if (new_x, new_y) not in from_a or a_to_x + 1 < from_a[(new_x, new_y)]: \n",
    "                            new_x_to_b = dis((new_x, new_y), tar) \n",
    "                            heapq.heappush(q, (a_to_x + 1 + new_x_to_b, new_x, new_y))\n",
    "                            from_a[(new_x, new_y)] = a_to_x + 1\n",
    "\n",
    "                    #if tar in from_a:\n",
    "                    #    return from_a[tar]\n",
    "            return -1\n",
    "\n",
    "        if forest[0][0] == 0:\n",
    "            return -1\n",
    "        pre = (0, 0)    \n",
    "        ans = 0\n",
    "        for num in nums:\n",
    "            cur = index[num]\n",
    "            d = A_star(pre, cur)\n",
    "            if d == -1:\n",
    "                return -1\n",
    "            ans += d\n",
    "            pre = cur\n",
    "              \n",
    "        return ans\n",
    "\n",
    "\n"
   ]
  }
 ],
 "metadata": {},
 "nbformat": 4,
 "nbformat_minor": 2
}
